package org.example.Soution003;

import java.util.*;

public class DynamicProgrammingLeastCombination {
    public static void main(String[] args) {
        DynamicProgrammingLeastCombination dp = new DynamicProgrammingLeastCombination();
        int[] nums=new int[]{411,412,413,414,415,416,417,418,419,420,421,422};
        System.out.println(dp.coinChange(nums,8863));
    }

    public int coinChange(int[] coins, int amount) {
        int max=amount+1;
        if(amount == 0) return 0;
        int[] res=new int[amount+1];
        Arrays.fill(res,max);
        res[0]=0;
        for(int i=1;i<=amount;i++){
            for(int coin:coins){
                if(coin<=i){
                    res[i]=Math.min(res[i],res[i-coin]+1);
                }
            }
        }
        System.out.println(Arrays.toString(res));
        return res[amount]>amount?-1:res[amount];
    }
}
